#ifndef NETEASE_GAME_H_
#define NETEASE_GAME_H_
#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
bool calculate(const char op, std::stack<int> &num, int n) {
	int r = 0;
	int cn, n2;
	switch (op) {
	case '+':
		while (n-- > 0) {
			cn = num.top();
			num.pop();
			r += cn;
		}
		num.push(r);
		break;
	case '-':
		if (n != 1 && n != 2)
			return false;
		if (n == 1) {
			n2 = num.top();
			num.pop();
			num.push(-n2);
			return true;
		}
			
		n2 = num.top();
		num.pop();

		cn = num.top();
		num.pop();
		r = cn - n2;
		num.push(r);
		break;
	case '*':
		if (n < 2)
			return false;
		r = 1;
		while (n-- > 0) {
			cn = num.top();
			num.pop();
			r *= cn;
		}
		num.push(r);
		break;
	}
	return true;
}

int readNumber(const std::string &s, int &i) {
	int r = s[i] - '0';
	//std::cout << r << std::endl;
	while (i++ < s.length()) {
		if (!isdigit(s[i]))
			break;
		int c = s[i] - '0';
		r = r * 10 + c;
	}
	i--;
	//std::cout << "read " << r << std::endl;
	return r;
}
std::string calcLisp(std::string s) {
	const std::string EMSG = "invalid expression";
	std::stack<char> oprt;
	std::stack<int> opnd, ops;
	std::string  r = "";
	bool hasOP = false;
	int opCount = 0;
	if (s[0] == '(')
		ops.push(0);
	else {
		return EMSG;
	}
	for (int i = 1; i < s.length(); i++) {
		char c = s[i];
		if (c == ' ')
			continue;
		if (c == '(') {
			hasOP = false;
			opCount = ops.top();
			ops.pop();
			ops.push(opCount + 1);
			ops.push(0);
			continue;
		}
		if (c == '+' || c == '-' || c == '*') {
			hasOP = true;
			oprt.push(c);
			continue;
		}
		if (c == ')') {
			hasOP = false;
			if (ops.empty()) {
				return EMSG;
			}
			bool result = calculate(oprt.top(), opnd, ops.top());
			if (!result)
				return EMSG;
			ops.pop();
			oprt.pop();
			continue;
		}
		if (isdigit(c)) {
			if (!hasOP) {
				return EMSG;
			}

			opCount = ops.top();
			ops.pop();
			ops.push(opCount + 1);
			int n = readNumber(s, i);
			opnd.push(n);
			continue;
		}
	}

	if (!ops.empty()) {
		return EMSG;
	}
	r = std::to_string(opnd.top());
	//calculate(oprt.top(), opnd);
	return r;
}

int calPrefix() {
	int n;
	std::string s;
	std::cin >> n;
	std::cin.get();
	std::vector<std::string> rs;
	while (n--) {
		std::getline(std::cin, s);
		//rs.push_back(calcLisp(s));
		std::cout << calcLisp(s) << std::endl;
	}
	/*for (int i = 0; i < rs.size(); i++) {
		std::cout << rs[i] << std::endl;
	}*/

	return 0;
}
#endif